home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / news / readers / nn-tk.001 / nn-tk~ / nn / hdbm.c < prev    next >
C/C++ Source or Header  |  1995-07-25  |  8KB  |  357 lines
  1. /*******************WARNING*********************
  2.  
  3. This is a *MODIFIED* version of Geoff Coller's proof-of-concept NOV
  4. implementation.
  5.  
  6. It has been modified to support threading directly from a file handle
  7. to a NNTP server without a temporary file.
  8.  
  9. This is not a complete distribution.  We have only distributed enough
  10. to support NN's needs.
  11.  
  12. The original version came from world.std.com:/src/news/nov.dist.tar.Z
  13. and was dated 11 Aug 1993.
  14.  
  15. In any case, bugs you find here are probably my fault, as I've trimmed
  16. a fair bit of unused code.
  17.  
  18. -Peter Wemm  <peter@DIALix.oz.au>
  19. */
  20.  
  21. /*
  22.  * Copyright (c) Geoffrey Collyer 1992, 1993.
  23.  * All rights reserved.
  24.  * Written by Geoffrey Collyer.
  25.  * Thanks to UUNET Communications Services Inc for financial support.
  26.  *
  27.  * This software is not subject to any license of the American Telephone
  28.  * and Telegraph Company, the Regents of the University of California, or
  29.  * the Free Software Foundation.
  30.  *
  31.  * Permission is granted to anyone to use this software for any purpose on
  32.  * any computer system, and to alter it and redistribute it freely, subject
  33.  * to the following restrictions:
  34.  *
  35.  * 1. The authors are not responsible for the consequences of use of this
  36.  *    software, no matter how awful, even if they arise from flaws in it.
  37.  *
  38.  * 2. The origin of this software must not be misrepresented, either by
  39.  *    explicit claim or by omission.  Since few users ever read sources,
  40.  *    credits must appear in the documentation.
  41.  *
  42.  * 3. Altered versions must be plainly marked as such, and must not be
  43.  *    misrepresented as being the original software.  Since few users
  44.  *    ever read sources, credits must appear in the documentation.
  45.  *
  46.  * 4. This notice may not be removed or altered.
  47.  */
  48.  
  49.  
  50. /*
  51.  * general-purpose in-core hashing, dbm interface
  52.  */
  53.  
  54. #include "config.h"
  55. #include "hdbm.h"
  56. #include "hdbmint.h"
  57.  
  58. /* tunable parameters */
  59. #define RETAIN 300        /* retain & recycle this many HASHENTs */
  60.  
  61. /* fundamental constants */
  62. #define YES 1
  63. #define NO 0
  64.  
  65. static HASHENT *hereuse = NULL;
  66. static int reusables = 0;
  67.  
  68. /*
  69.  * Gosling EMACS hash (h = 33*h + *s++) optimized, loop unrolled with
  70.  * "Duff's Device".  Thanks to Chris Torek.
  71.  */
  72. static unsigned
  73. hdbmdef(key)
  74. register HDBMDATUM key;
  75. {
  76.     register unsigned char *s = (unsigned char *)key.dat_ptr;
  77.     register int len = key.dat_len;
  78.     register unsigned h;
  79.     register int loop;
  80.  
  81. #define HASHC   h = (h << 5) + h + *s++;
  82.  
  83.     h = 0;
  84.     if (len > 0) {
  85.         loop = (len + 8 - 1) >> 3;
  86.  
  87.         switch (len & (8 - 1)) {
  88.         case 0:
  89.             do {    /* All fall throughs */
  90.                 HASHC;
  91.         case 7:
  92.                 HASHC;
  93.         case 6:
  94.                 HASHC;
  95.         case 5:
  96.                 HASHC;
  97.         case 4:
  98.                 HASHC;
  99.         case 3:
  100.                 HASHC;
  101.         case 2:
  102.                 HASHC;
  103.         case 1:
  104.                 HASHC;
  105.             } while (--loop);
  106.         }
  107.  
  108.     }
  109.     return (h);
  110. }
  111.  
  112. HASHTABLE *
  113. hdbmcreate(size, hashfunc)
  114. register unsigned size;            /* a crude guide to size */
  115. unsigned (*hashfunc)();
  116. {
  117.     register HASHTABLE *tbl;
  118.     register HASHENT **hepp;
  119.     /*
  120.      * allocate HASHTABLE and (HASHENT *) array together to reduce the
  121.      * number of malloc calls.  this idiom ensures correct alignment of
  122.      * the array.
  123.      * dmr calls the one-element array trick `unwarranted chumminess with
  124.      * the compiler' though.
  125.      */
  126.     register struct alignalloc {
  127.         HASHTABLE ht;
  128.         HASHENT *hepa[1];    /* longer than it looks */
  129.     } *aap;
  130.  
  131.     aap = (struct alignalloc *)
  132.         malloc(sizeof *aap + (size-1)*sizeof(HASHENT *));
  133.     if (aap == NULL)
  134.         return NULL;
  135.     tbl = &aap->ht;
  136.     tbl->ht_size = (size == 0? 1: size);    /* size of 0 is nonsense */
  137.     tbl->ht_magic = HASHMAG;
  138.     tbl->ht_hash = (hashfunc == NULL? hdbmdef: hashfunc);
  139.     tbl->ht_addr = hepp = aap->hepa;
  140.     while (size-- > 0)
  141.         hepp[size] = NULL;
  142.     return tbl;
  143. }
  144.  
  145. static void
  146. hefree(hp)                    /* free a hash entry */
  147. register HASHENT *hp;
  148. {
  149.     if (reusables >= RETAIN)        /* compost heap is full? */
  150.         free((char *)hp);        /* yup, just pitch this one */
  151.     else {                    /* no, just stash for reuse */
  152.         ++reusables;
  153.         hp->he_next = hereuse;
  154.         hereuse = hp;
  155.     }
  156. }
  157.  
  158. /*
  159.  * free all the memory associated with tbl, erase the pointers to it, and
  160.  * invalidate tbl to prevent further use via other pointers to it.
  161.  */
  162. void
  163. hdbmdestroy(tbl)
  164. register HASHTABLE *tbl;
  165. {
  166.     register unsigned idx;
  167.     register HASHENT *hp, *next;
  168.     register HASHENT **hepp;
  169.     register int tblsize;
  170.  
  171.     if (tbl == NULL || BADTBL(tbl))
  172.         return;
  173.     tblsize = tbl->ht_size;
  174.     hepp = tbl->ht_addr;
  175.     for (idx = 0; idx < tblsize; idx++) {
  176.         for (hp = hepp[idx]; hp != NULL; hp = next) {
  177.             next = hp->he_next;
  178.             hp->he_next = NULL;
  179.             hefree(hp);
  180.         }
  181.         hepp[idx] = NULL;
  182.     }
  183.     tbl->ht_magic = 0;        /* de-certify this table */
  184.     tbl->ht_addr = NULL;
  185.     free((char *)tbl);
  186. }
  187.  
  188. /*
  189.  * The returned value is the address of the pointer that refers to the
  190.  * found object.  Said pointer may be NULL if the object was not found;
  191.  * if so, this pointer should be updated with the address of the object
  192.  * to be inserted, if insertion is desired.
  193.  */
  194. static HASHENT **
  195. hdbmfind(tbl, key)
  196. register HASHTABLE *tbl;
  197. HDBMDATUM key;
  198. {
  199.     register HASHENT *hp, *prevhp = NULL;
  200.     register char *hpkeydat, *keydat = key.dat_ptr;
  201.     register int keylen = key.dat_len;
  202.     register HASHENT **hepp;
  203.     register unsigned size; 
  204.  
  205.     if (BADTBL(tbl))
  206.         return NULL;
  207.     size = tbl->ht_size;
  208.     if (size == 0)            /* paranoia: avoid division by zero */
  209.         size = 1;
  210.     hepp = &tbl->ht_addr[(*tbl->ht_hash)(key) % size];
  211.     for (hp = *hepp; hp != NULL; prevhp = hp, hp = hp->he_next) {
  212.         hpkeydat = hp->he_key.dat_ptr;
  213.         if (hp->he_key.dat_len == keylen && hpkeydat[0] == keydat[0] &&
  214.             memcmp(hpkeydat, keydat, keylen) == 0)
  215.             break;
  216.     }
  217.     /* assert: *(returned value) == hp */
  218.     return (prevhp == NULL? hepp: &prevhp->he_next);
  219. }
  220.  
  221. static HASHENT *
  222. healloc()                    /* allocate a hash entry */
  223. {
  224.     register HASHENT *hp;
  225.  
  226.     if (hereuse == NULL)
  227.         return (HASHENT *)malloc(sizeof(HASHENT));
  228.     /* pull the first reusable one off the pile */
  229.     hp = hereuse;
  230.     hereuse = hereuse->he_next;
  231.     hp->he_next = NULL;            /* prevent accidents */
  232.     reusables--;
  233.     return hp;
  234. }
  235.  
  236. int
  237. hdbmstore(tbl, key, data)
  238. register HASHTABLE *tbl;
  239. HDBMDATUM key, data;
  240. {
  241.     register HASHENT *hp;
  242.     register HASHENT **nextp;
  243.  
  244.     if (BADTBL(tbl))
  245.         return NO;
  246.     nextp = hdbmfind(tbl, key);
  247.     if (nextp == NULL)
  248.         return NO;
  249.     hp = *nextp;
  250.     if (hp == NULL) {            /* absent; allocate an entry */
  251.         hp = healloc();
  252.         if (hp == NULL)
  253.             return NO;
  254.         hp->he_next = NULL;
  255.         hp->he_key = key;
  256.         *nextp = hp;            /* append to hash chain */
  257.     }
  258.     hp->he_data = data;    /* supersede any old data for this key */
  259.     return YES;
  260. }
  261.  
  262. /* return any existing entry for key; otherwise call allocator to make one */
  263. HDBMDATUM
  264. hdbmentry(tbl, key, allocator)
  265. register HASHTABLE *tbl;
  266. HDBMDATUM key;
  267. HDBMDATUM (*allocator)();
  268. {
  269.     register HASHENT *hp;
  270.     register HASHENT **nextp;
  271.     static HDBMDATUM errdatum = { NULL, 0 };
  272.  
  273.     if (BADTBL(tbl))
  274.         return errdatum;
  275.     nextp = hdbmfind(tbl, key);
  276.     if (nextp == NULL)
  277.         return errdatum;
  278.     hp = *nextp;
  279.     if (hp == NULL) {            /* absent; allocate an entry */
  280.         hp = healloc();
  281.         if (hp == NULL)
  282.             return errdatum;
  283.         hp->he_next = NULL;
  284.         hp->he_key = key;
  285.         hp->he_data = (*allocator)(key);
  286.         *nextp = hp;            /* append to hash chain */
  287.     }
  288.     return hp->he_data;
  289. }
  290.  
  291. int
  292. hdbmdelete(tbl, key)
  293. register HASHTABLE *tbl;
  294. HDBMDATUM key;
  295. {
  296.     register HASHENT *hp;
  297.     register HASHENT **nextp;
  298.  
  299.     nextp = hdbmfind(tbl, key);
  300.     if (nextp == NULL)
  301.         return NO;
  302.     hp = *nextp;
  303.     if (hp == NULL)                /* absent */
  304.         return NO;
  305.     *nextp = hp->he_next;            /* skip this entry */
  306.     hp->he_next = NULL;
  307.     hp->he_data.dat_ptr = hp->he_key.dat_ptr = NULL;
  308.     hefree(hp);
  309.     return YES;
  310. }
  311.  
  312. HDBMDATUM                    /* data corresponding to key */
  313. hdbmfetch(tbl, key)
  314. register HASHTABLE *tbl;
  315. HDBMDATUM key;
  316. {
  317.     register HASHENT *hp;
  318.     register HASHENT **nextp;
  319.     static HDBMDATUM errdatum = { NULL, 0 };
  320.  
  321.     if (BADTBL(tbl))
  322.         return errdatum;
  323.     nextp = hdbmfind(tbl, key);
  324.     if (nextp == NULL)
  325.         return errdatum;
  326.     hp = *nextp;
  327.     if (hp == NULL)                /* absent */
  328.         return errdatum;
  329.     else
  330.         return hp->he_data;
  331. }
  332.  
  333. /*
  334.  * visit each entry by calling nodefunc at each, with key, data and hook as
  335.  * arguments.  hook is an attempt to allow side-effects and reentrancy at
  336.  * the same time.
  337.  */
  338. void
  339. hdbmwalk(tbl, nodefunc, hook)
  340. HASHTABLE *tbl;
  341. register int (*nodefunc)();
  342. register char *hook;                /* (void *) really */
  343. {
  344.     register unsigned idx;
  345.     register HASHENT *hp;
  346.     register HASHENT **hepp;
  347.     register int tblsize;
  348.  
  349.     if (BADTBL(tbl))
  350.         return;
  351.     hepp = tbl->ht_addr;
  352.     tblsize = tbl->ht_size;
  353.     for (idx = 0; idx < tblsize; idx++)
  354.         for (hp = hepp[idx]; hp != NULL; hp = hp->he_next)
  355.             (*nodefunc)(hp->he_key, hp->he_data, hook);
  356. }
  357.